Internet Protocol (IP) address lookup is a bottleneck in the performance of routers and switches operating on the Internet. Expectations are for the bottleneck to worsen with increasingly larger routing tables, faster communication links, heavier packet traffic, and the migration from 32-bit Internet Protocol Version 4 (IPv4) addresses to 128-bit Internet Protocol Version 6 (IPv6) addresses. Consequently, it is becoming increasingly important for routers and switches to employ IP packet forwarding that can meet these increasing demands.
FIG. 1 illustrates a network including a router 20. The router 20 receives IP packets 22 from a node (NODE A) in the network. Each received IP packet 22 has a header 24 and data 28. The header 24 includes a destination address field 26, which has an IP address of a node (or host) to which the IP packet 22 is targeted. With this IP address, the router 20 accesses a forwarding table 32 to determine to which node to forward the IP packet 20. In general, the selected node is that which advances the IP packet 22 towards its destination.
A technique for implementing a forwarding table is to use a longest prefix matching (LPM) algorithm. A basic principle of IP addressing is that routers and switches can use the prefixes of an IP address to make routing decisions. A familiar dot-notation for a 32-bit IP address includes four decimal values separated by periods (e.g., 208.128.16.10). Each decimal value is represented by 8 bits (a byte). The leftmost 16 bits of the IP address can, for example, identify a corporation, the leftmost 20 bits of the IP address an office in that corporation, the leftmost 24 bits a particular network (e.g., Ethernet) in that office, and all 32 bits a particular host device on that network.
When performing the LPM algorithm, the router 20 compares the destination address 26 to entries in the forwarding table 32 to find the entry with the longest matching prefix. That entry indicates the location (or node) towards which to send the IP packet 22. For example, consider that the router 20 receives an IP packet 22 with a destination address of 208.128.16.10 and upon searching the forwarding table 32 finds two entries with matching prefixes, the first entry being 208.128 and the second entry being 208.128.16. The router 20 then selects the second entry (208.128.16) because it is longer than the first entry.
One way to implement the LPM algorithm is to use a prefix tree (i.e., a binary tree) having a root node, intermediate nodes, and leaf nodes. The leaf nodes represent prefix entries in the forwarding table 32. The prefix tree is built only to the extent needed to represent all of the entries in the forwarding table 32. The router 20 searches for the longest prefix in the prefix tree that matches part of or the entire destination IP address 26 by traversing the prefix tree from root node to a leaf node, possibly passing through one or more intermediate nodes. Each node traversed adds a bit to the matching prefix. From a leaf node the router 20 obtains the forwarding location. A disadvantage of using a direct implementation of the prefix tree is that the process can require a traversal of as many nodes as there are bits in the IP address to obtain the forwarding location. Thus there is a need for improving implementations that use the longest prefix matching algorithm for forwarding IP packets.